struct SCC {
  SCC() {}
  SCC(int _n) : n_(_n), adj_(_n), bel_(_n, -1), low_(_n), dfn_(_n, -1), ins_(_n), tim_(0), cor_(0) {}

  void addEdge(int x, int y) {
    adj_[x].push_back(y);
  }

  void dfs(int x) {
    dfn_[x] = low_[x] = ++tim_;
    ins_[x] = true;
    stk_.push_back(x);

    for (auto &y : adj_[x]) {
      if (dfn_[y] == -1) {
        dfs(y);
        low_[x] = min(low_[x], low_[y]);
      } else {
        if (ins_[y]) {
          low_[x] = min(low_[x], dfn_[y]);
        }
      }
    }

    if (dfn_[x] == low_[x]) {
      int y;
      do {
        y = stk_.back();
        bel_[y] = cor_;
        ins_[y] = false;
        stk_.pop_back();
      } while (y != x);
      cor_++;
    }
  }

  vector<int> work() {
    for (int i = 0; i < n_; i++) {
      if (dfn_[i] == -1) {
        dfs(i);
      }
    }
    return bel_;
  }

  vector<vector<int>> adj_;
  vector<int> stk_, dfn_, low_, bel_;
  vector<bool> ins_;
  int tim_, cor_, n_;
};